// function merge(nums1, m, nums2, n) {
//   nums1.splice(m, nums1.length - m);
//   nums2.splice(n, nums2.length - n);
//   nums1 = nums1.concat(nums2);
//   nums1.sort((a, b) => a - b);
//   console.log(nums1);
//   return nums1;
// }
// const nums1 = [1, 2, 3, 0, 0, 0],
//   m = 3,
//   nums2 = [2, 5, 6],
//   n = 3;
// const res = merge(nums1, m, nums2, n);
// console.log(res);

/**
 * 上面解答的问题：
 * 原数组未被修改：代码里借助 concat 方法生成了新数组，再把它赋值给 nums1。
 * 然而，这只是让 nums1 这个变量指向了新数组，原始传入的 nums1 数组并未被修改。
 * 根据题目的要求，需要直接在 nums1 数组上进行修改。
 * 函数不需要返回值：题目明确说明最终合并后的数组应存于 nums1 中，而不是由函数返回。
 */

/**
 * 1.暴力解决法（直接合并后排序）
 * 时间复杂度O((m+n)log(m+n))
 * 排序长度为m + n,套用快速排序的时间复杂度即可
 * 空间复杂度O((m+n)log(m+n))
 * 排序长度为m+n,套用快速排序的空间复杂度即可
 */

// function merge(nums1, m, nums2, n) {
//   nums1.splice(m, nums1.length - m, ...nums2);
//   nums1.sort((a, b) => a - b);
// }
// let nums1 = [1, 2, 3, 0, 0, 0],
//   m = 3,
//   nums2 = [2, 5, 6],
//   n = 3;
// merge(nums1, m, nums2, n);
// console.log(nums1);

/**
 * 双指针法
 * 1.可以利用原数组排序的性质
 * 2.设置两个指针，分别指向nums1和nums2
 * 3.判断两个指针指向的元素大小，添加到新的数组里
 * 4.将新数组的元素依次赋值给nums1，改变nums1
 * 时间复杂度O(m+n)
 * 指针移动单调递增，最多移动m + n次
 * 空间复杂度O(m+n)
 * 需要创立长度为m + n的中间数组
 */
function merge(nums1, m, nums2, n) {
  // 定义两个指针
  let p1 = 0,
    p2 = 0;
  let newArr = new Array(m + n).fill(0);
  // 定义一个中间变量接受元素
  let midElement;
  // 结束条件：两个指针指向的元素超出两个数组的长度
  while (p1 < m || p2 < n) {
    if (p1 === m) {
      midElement = nums2[p2++];
    } else if (p2 === n) {
      midElement = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      midElement = nums1[p1++];
    } else {
      midElement = nums2[p2++];
    }
    newArr[p1 + p2 - 1] = midElement;
  }

  // 改变nums1的数组
  for (let i = 0; i < m + n; i++) {
    nums1[i] = newArr[i];
  }
}
let nums1 = [1, 2, 3, 0, 0, 0],
  m = 3,
  nums2 = [2, 5, 6],
  n = 3;
merge(nums1, m, nums2, n);
console.log(nums1);
